//
// Created by Lenovo on 2025/11/25.
//

#include "KeyPath.h"
#include<stdlib.h>
#include<cstring>
#include <iostream>
using namespace std;

static int topologicalOrder(const ArcGraph* graph,int* ETV,int* LTV) {
    int count=0;
    int* inDegree = static_cast<int *>(malloc(sizeof(int)*graph->nodeNum));
    if (!inDegree) {
        return -1;
    }
    memset(inDegree,0,sizeof(int)*graph->nodeNum);
    for (int i = 0; i < graph->nodeNum; i++) {
        if (graph->node[i].firstEdge) {
            ArcEdge* edge = graph->node[i].firstEdge;
            while (edge) {
                ++inDegree[edge->no];
                edge = edge->next;
            }
        }
    }
    int *stack = new int[graph->nodeNum];
    int *outDegree = new int[graph->nodeNum];//存出栈元素
    int top = -1;
    for (int i = 0; i < graph->nodeNum; i++) {
        if (inDegree[i] == 0) {
            stack[++top] = i;
            break;               //关键路径中默认源点只有一个
        }
    }
    int tmp = 0;
    int index = 0;//记录排序结果的情况
    while (top!=-1) {
        tmp = stack[top--];
        outDegree[index++] = inDegree[tmp];
        ArcEdge* edge = graph->node[tmp].firstEdge;
        while (edge) {
            --inDegree[edge->no];
            ++count;
            if (inDegree[edge->no] == 0) {
                stack[++top] = edge->no;
            }
            if (ETV[tmp] + edge->weight> ETV[edge->no] ) {
                ETV[edge->no] = ETV[tmp] + edge->weight;
            }
            edge = edge->next;
        }
    }
    free(stack);
    free(outDegree);
    free(inDegree);
    if (count < graph->nodeNum) {
        return -1;
    }
    return 0;
}
void KeyPath(ArcGraph *graph) {
//1、计算顶点ETV&LTV
    int* ETV = static_cast<int *>(malloc(sizeof(int) * graph->nodeNum));
    int* LTV = (int*)malloc(sizeof(int)*graph->nodeNum);
    memset(LTV,0,sizeof(int)*graph->nodeNum);
    memset(ETV,0,sizeof(int)*graph->nodeNum);
    //2、更新ETE&LTE，直接输出值
    for (int i = 0; i < graph->nodeNum; i++) {
        ArcEdge* edge = graph->node[i].firstEdge;
        while (edge) {
            if (ETV[i]==LTV[edge->no]+edge->weight) { //ETE的值为弧头ETV的值；LTE的值为弧尾LTV的值减边的权值；ETE=LTE时则为关键活动
                cout<<graph->node[i].no<<" "<<edge->weight<<" "<<graph->node[edge->no].no<<endl;
            }
            edge = edge->next;
        }
    }
    free(ETV);
    free(LTV);
}
